package leetcode.p149;

/**
 * @author: trtan
 * @date: 2021-06-24 12:26
 **/
public class MaxPointsOnLine {
    /**
     * 任意两个不同的点可以确定一条直线 即(x1,y1) (x2,y2) =>
     * (x-x1)/(x2-x1)=(y-y1)/(y2-y1) => (x-x1)(y2-y1)=(y-y1)(x2-x1)
     * @param points
     * @return int
     * @author trtan
     * @date 2021/6/24 12:30
     */
    public int maxPoints(int[][] points) {
        int n = points.length;
        int result = Math.min(2, n);
        for (int i = 0; i < n; i++) {
            int x_1 = points[i][0];
            int y_1 = points[i][1];
            for (int j = i + 1; j < n; j++) {
                int x_2 = points[j][0];
                int y_2 = points[j][1];
                int count = 2;
                for (int k = 0; k < n; k++) {
                    if (k == i || k == j) {
                        continue;
                    }
                    int x = points[k][0];
                    int y = points[k][1];
                    if ((x - x_1) * (y_2 - y_1) == (y-y_1) * (x_2 - x_1)) {
                        count++;
                    }
                }
                result = Math.max(result, count);
            }
        }
        return result;
    }
}
